<?xml version="1.0" encoding="ascii"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
          "DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
  <title>equivalence.Equivalence</title>
  <link rel="stylesheet" href="epydoc.css" type="text/css" />
  <script type="text/javascript" src="epydoc.js"></script>
</head>

<body bgcolor="white" text="black" link="blue" vlink="#204080"
      alink="#204080">
<!-- ==================== NAVIGATION BAR ==================== -->
<table class="navbar" border="0" width="100%" cellpadding="0"
       bgcolor="#a0c0ff" cellspacing="0">
  <tr valign="middle">
  <!-- Home link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="equivalence-module.html">Home</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Tree link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="module-tree.html">Trees</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Index link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="identifier-index.html">Indices</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Help link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="help.html">Help</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Project homepage -->
      <th class="navbar" align="right" width="100%">
        <table border="0" cellpadding="0" cellspacing="0">
          <tr><th class="navbar" align="center"
            >equivalence</th>
          </tr></table></th>
  </tr>
</table>
<table width="100%" cellpadding="0" cellspacing="0">
  <tr valign="top">
    <td width="100%">
      <span class="breadcrumbs">
        <a href="equivalence-module.html">Module&nbsp;equivalence</a> ::
        Class&nbsp;Equivalence
      </span>
    </td>
    <td>
      <table cellpadding="0" cellspacing="0">
        <!-- hide/show private -->
        <tr><td align="right"><span class="options">[<a href="javascript:void(0);" class="privatelink"
    onclick="toggle_private();">hide&nbsp;private</a>]</span></td></tr>
        <tr><td align="right"><span class="options"
            >[<a href="frames.html" target="_top">frames</a
            >]&nbsp;|&nbsp;<a href="equivalence.Equivalence-class.html"
            target="_top">no&nbsp;frames</a>]</span></td></tr>
      </table>
    </td>
  </tr>
</table>
<!-- ==================== CLASS DESCRIPTION ==================== -->
<h1 class="epydoc">Class Equivalence</h1><span class="codelink"><a href="equivalence-pysrc.html#Equivalence">source&nbsp;code</a></span><br /><br />
<pre class="base-tree">
object --+
         |
        <strong class="uidshort">Equivalence</strong>
</pre>

<dl><dt>Known Subclasses:</dt>
<dd>
    <a href="equivalence.BidirectionalEquivalence-class.html">BidirectionalEquivalence</a>,
    <a href="equivalence.KeyEquivalence-class.html">KeyEquivalence</a>
</dd></dl>

<hr />
<p>Basic equivalence relation.</p>
<p>An <a href="equivalence.Equivalence-class.html" class="link">Equivalence</a> instance maintains a partition of objects into sets so that
the equivalence properties (reflexivity, symmetry, transitivity) are preserved.
Two objects <tt class="rst-docutils literal"><span class="pre">a</span></tt> and <tt class="rst-docutils literal"><span class="pre">b</span></tt> are considered equivalent after <a href="equivalence.Equivalence-class.html#merge" class="link">merge(a,b)</a>.</p>
<p>This implementation uses a <a class="rst-reference" href="http://en.wikipedia.org/wiki/Disjoint-set_data_structure" target="_top">disjoint-set forests</a> data structure with
<em>union by rank</em> and <em>path compression</em> so most operations have almost
constant amortized time. The main exception is <a href="equivalence.Equivalence-class.html#partition" class="link">partition</a>, which is linear
to the size of the <strong>whole equivalence</strong> and should therefore be avoided for
large relations.</p><br /><br />

<!-- ==================== INSTANCE METHODS ==================== -->
<a name="section-InstanceMethods"></a>
<table class="summary" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr bgcolor="#70b0f0" class="table-header">
  <td colspan="2" class="table-header">
    <table border="0" cellpadding="0" cellspacing="0" width="100%">
      <tr valign="top">
        <td align="left"><span class="table-header">Instance Methods</span></td>
        <td align="right" valign="top"
         ><span class="options">[<a href="#section-InstanceMethods"
         class="privatelink" onclick="toggle_private();"
         >hide private</a>]</span></td>
      </tr>
    </table>
  </td>
</tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="equivalence.Equivalence-class.html#__init__" class="summary-sig-name">__init__</a>(<span class="summary-sig-arg">self</span>)</span><br />
      Intialize this equivalence.</td>
          <td align="right" valign="top">
            <span class="codelink"><a href="equivalence-pysrc.html#Equivalence.__init__">source&nbsp;code</a></span>
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a name="update"></a><span class="summary-sig-name">update</span>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">*objects</span>)</span><br />
      Update this equivalence with the given objects.</td>
          <td align="right" valign="top">
            <span class="codelink"><a href="equivalence-pysrc.html#Equivalence.update">source&nbsp;code</a></span>
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a name="merge"></a><span class="summary-sig-name">merge</span>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">*objects</span>)</span><br />
      Merge all the given objects into the same equivalence set.</td>
          <td align="right" valign="top">
            <span class="codelink"><a href="equivalence-pysrc.html#Equivalence.merge">source&nbsp;code</a></span>
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">bool</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="equivalence.Equivalence-class.html#are_equivalent" class="summary-sig-name">are_equivalent</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">*objects</span>)</span><br />
      Check whether all objects are equivalent.</td>
          <td align="right" valign="top">
            <span class="codelink"><a href="equivalence-pysrc.html#Equivalence.are_equivalent">source&nbsp;code</a></span>
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">list of lists</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="equivalence.Equivalence-class.html#partitions" class="summary-sig-name">partitions</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">objects</span>=<span class="summary-sig-default">None</span>)</span><br />
      Return the partitioning of <code class="link">objects</code> into equivalence groups.</td>
          <td align="right" valign="top">
            <span class="codelink"><a href="equivalence-pysrc.html#Equivalence.partitions">source&nbsp;code</a></span>
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">set</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="equivalence.Equivalence-class.html#partition" class="summary-sig-name">partition</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">obj</span>)</span><br />
      Return the set of objects in the equivalence that are equivalent to
<code class="link">obj</code>.</td>
          <td align="right" valign="top">
            <span class="codelink"><a href="equivalence-pysrc.html#Equivalence.partition">source&nbsp;code</a></span>
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr class="private">
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="equivalence.Equivalence-class.html#_find" class="summary-sig-name">_find</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">obj</span>,
        <span class="summary-sig-arg">insert_if_missing</span>=<span class="summary-sig-default">False</span>)</span><br />
      The 'find' part of the union-find algorithm.</td>
          <td align="right" valign="top">
            <span class="codelink"><a href="equivalence-pysrc.html#Equivalence._find">source&nbsp;code</a></span>
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr class="private">
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a name="_join"></a><span class="summary-sig-name">_join</span>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">obj</span>,
        <span class="summary-sig-arg">parent</span>=<span class="summary-sig-default">None</span>)</span><br />
      Join <code class="link">obj</code> to its parent (or None if it's the root).</td>
          <td align="right" valign="top">
            <span class="codelink"><a href="equivalence-pysrc.html#Equivalence._join">source&nbsp;code</a></span>
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr class="private">
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a name="_iter_objects"></a><span class="summary-sig-name">_iter_objects</span>(<span class="summary-sig-arg">self</span>)</span><br />
      Return an iterator over all the objects of the equivalence.</td>
          <td align="right" valign="top">
            <span class="codelink"><a href="equivalence-pysrc.html#Equivalence._iter_objects">source&nbsp;code</a></span>
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
  <tr>
    <td colspan="2" class="summary">
    <p class="indent-wrapped-lines"><b>Inherited from <code>object</code></b>:
      <code>__delattr__</code>,
      <code>__getattribute__</code>,
      <code>__hash__</code>,
      <code>__new__</code>,
      <code>__reduce__</code>,
      <code>__reduce_ex__</code>,
      <code>__repr__</code>,
      <code>__setattr__</code>,
      <code>__str__</code>
      </p>
    </td>
  </tr>
</table>
<!-- ==================== PROPERTIES ==================== -->
<a name="section-Properties"></a>
<table class="summary" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr bgcolor="#70b0f0" class="table-header">
  <td colspan="2" class="table-header">
    <table border="0" cellpadding="0" cellspacing="0" width="100%">
      <tr valign="top">
        <td align="left"><span class="table-header">Properties</span></td>
        <td align="right" valign="top"
         ><span class="options">[<a href="#section-Properties"
         class="privatelink" onclick="toggle_private();"
         >hide private</a>]</span></td>
      </tr>
    </table>
  </td>
</tr>
  <tr>
    <td colspan="2" class="summary">
    <p class="indent-wrapped-lines"><b>Inherited from <code>object</code></b>:
      <code>__class__</code>
      </p>
    </td>
  </tr>
</table>
<!-- ==================== METHOD DETAILS ==================== -->
<a name="section-MethodDetails"></a>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr bgcolor="#70b0f0" class="table-header">
  <td colspan="2" class="table-header">
    <table border="0" cellpadding="0" cellspacing="0" width="100%">
      <tr valign="top">
        <td align="left"><span class="table-header">Method Details</span></td>
        <td align="right" valign="top"
         ><span class="options">[<a href="#section-MethodDetails"
         class="privatelink" onclick="toggle_private();"
         >hide private</a>]</span></td>
      </tr>
    </table>
  </td>
</tr>
</table>
<a name="__init__"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">__init__</span>(<span class="sig-arg">self</span>)</span>
    <br /><em class="fname">(Constructor)</em>
  </h3>
  </td><td align="right" valign="top"
    ><span class="codelink"><a href="equivalence-pysrc.html#Equivalence.__init__">source&nbsp;code</a></span>&nbsp;
    </td>
  </table>
  
  Intialize this equivalence.
  <dl class="fields">
    <dt>Overrides:
      object.__init__
    </dt>
  </dl>
</td></tr></table>
</div>
<a name="are_equivalent"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">are_equivalent</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">*objects</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    ><span class="codelink"><a href="equivalence-pysrc.html#Equivalence.are_equivalent">source&nbsp;code</a></span>&nbsp;
    </td>
  </table>
  
  <p>Check whether all objects are equivalent.</p>
<p>An object doesn't have to be in the equivalence (through <a href="equivalence.Equivalence-class.html#update" class="link">update</a> or
<a href="equivalence.Equivalence-class.html#merge" class="link">merge</a>) in order to appear as an argument.</p>
  <dl class="fields">
    <dt>Returns: bool</dt>
  </dl>
</td></tr></table>
</div>
<a name="partitions"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">partitions</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">objects</span>=<span class="sig-default">None</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    ><span class="codelink"><a href="equivalence-pysrc.html#Equivalence.partitions">source&nbsp;code</a></span>&nbsp;
    </td>
  </table>
  
  Return the partitioning of <code class="link">objects</code> into equivalence groups.
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>objects</code></strong> (Iterable or None) - If not None, it must be an iterable of objects to be
partitioned. Otherwise, it defaults to the objects already inserted
in the equivalence (through <a href="equivalence.Equivalence-class.html#update" class="link">update</a> and <a href="equivalence.Equivalence-class.html#merge" class="link">merge</a>).</li>
    </ul></dd>
    <dt>Returns: list of lists</dt>
        <dd>A list of partitions, each partition being a list of equivalent
objects. Note that if the passed argument contains duplicates, so
will the respective partition list, i.e. the partition is not a set.</dd>
  </dl>
</td></tr></table>
</div>
<a name="partition"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">partition</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">obj</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    ><span class="codelink"><a href="equivalence-pysrc.html#Equivalence.partition">source&nbsp;code</a></span>&nbsp;
    </td>
  </table>
  
  Return the set of objects in the equivalence that are equivalent to
<code class="link">obj</code>.
  <dl class="fields">
    <dt>Returns: set</dt>
  </dl>
<div class="fields">      <p><strong>Attention:</strong>
        This implementation is linear to the number of objects in the
equivalence. If you call this a lot, you might want to use a
<a href="equivalence.BidirectionalEquivalence-class.html" class="link">BidirectionalEquivalence</a> instance instead.
      </p>
</div></td></tr></table>
</div>
<a name="_find"></a>
<div class="private">
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">_find</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">obj</span>,
        <span class="sig-arg">insert_if_missing</span>=<span class="sig-default">False</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    ><span class="codelink"><a href="equivalence-pysrc.html#Equivalence._find">source&nbsp;code</a></span>&nbsp;
    </td>
  </table>
  
  The 'find' part of the union-find algorithm.
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>obj</code></strong> - The object whose tree root is to be returned.</li>
        <li><strong class="pname"><code>insert_if_missing</code></strong> (bool) - If true and <code class="link">obj</code> is not already in this
equivalence, add it as a new singleton tree.</li>
    </ul></dd>
    <dt>Returns:</dt>
        <dd>The root of <code class="link">obj</code>'s tree.</dd>
  </dl>
</td></tr></table>
</div>
<br />
<!-- ==================== NAVIGATION BAR ==================== -->
<table class="navbar" border="0" width="100%" cellpadding="0"
       bgcolor="#a0c0ff" cellspacing="0">
  <tr valign="middle">
  <!-- Home link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="equivalence-module.html">Home</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Tree link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="module-tree.html">Trees</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Index link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="identifier-index.html">Indices</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Help link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="help.html">Help</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Project homepage -->
      <th class="navbar" align="right" width="100%">
        <table border="0" cellpadding="0" cellspacing="0">
          <tr><th class="navbar" align="center"
            >equivalence</th>
          </tr></table></th>
  </tr>
</table>
<table border="0" cellpadding="0" cellspacing="0" width="100%%">
  <tr>
    <td align="left" class="footer">
    Generated by Epydoc 3.0beta1 on Tue Jun 03 17:28:11 2008
    </td>
    <td align="right" class="footer">
      <a href="http://epydoc.sourceforge.net">http://epydoc.sourceforge.net</a>
    </td>
  </tr>
</table>

<script type="text/javascript">
  <!--
  // Private objects are initially displayed (because if
  // javascript is turned off then we want them to be
  // visible); but by default, we want to hide them.  So hide
  // them unless we have a cookie that says to show them.
  checkCookie()
  // -->
</script>
  
</body>
</html>
